A common form of an information retrieval system for managing computerized records contained in a database is a relational database management system. Between an actual database (that is, data stored for use by a computer) and users of an information retrieval system for managing is a software layer known as the relational database management system (RDBMS or DBMS). The RDBMS is responsible for handling all requests for access to the database and shielding the users from the details of any specific hardware and/or software implementation. Using relational techniques, the RDBMS stores, manipulates and retrieves data in table form. Typically, these relationships are defined by a set of columns and a set of rows. The columns are also referred to as attributes, or data types. The rows are also referred to as records or tuples, of data.
A standard language for dealing with DBMSs is the Structured Query Language (SQL). SQL comprises both data definition operations and data manipulation operations. To maintain data independence, a set of SQL commands, referred to as a query, provides the RDBMS with instructions to perform. However, the query does not describe directions for performing the instructions. Thus, the RDBMS comprises a query processor for generating various query plans of execution and choosing a preferred plan. Due to the high-level nature of relational expressions and a variety of implementation techniques, automatic query optimization is possible and often necessary to ensure efficient query processing.
In accordance with well-known query translation processes, an SQL query is processed in stages. The initial stage casts the source query into an internal form such as the Query Graph Model (QGM) following the preliminary steps of lexing, parsing and semantic checking. The goal of the QGM is to provide a more powerful and conceptually more manageable representation of queries to reduce the complexity of query compilation and optimization. The internal QGM is a data structure for providing the semantic relationships of the query for use by query translator and optimizer components for rewriting the query in a canonical form. A plan optimizer produces a query execution plan such as by generating alternate plans and choosing a best plan based on estimated execution costs. A plan refinement stage may be employed to refine the optimum execution plan in accordance with run-time requirements.
Often, for the query results to be utilized in a meaningful way, the query is also sorted. However, database tables can be very large and processing tables for sorting can be expensive in terms of computer resources. Therefore, it is important that techniques for sorting tables be as efficient as possible.
Known database systems provide a sorting operation that executes completely on a table. That is, when a sorting operation is used in executing an application such as a query plan in a database system, output rows are returned from the sorting operation only when the sorting operation has been executed on the entire table. Thus, the sorting operation acts as a barrier for outputting rows. Consequently, the application or query waits until the sorting operation is completed before receiving any sorted rows. This waiting period increases the application execution time, which may be especially high for external sorting operations. External sorting operations are generally performed when the data to be sorted is too large to place in a main memory. Such sorting operations seek to minimize disk accesses for the sort. What is therefore needed is a system and associated method that reduce the waiting time for sorting operations executed on tables. The need for such system and method has heretofore remained unsatisfied.